#!/python
# Author DuZhe <duzhe0211@gmail.com>
# Date 2013-02-04

from math import pow
import random

def factorial(n):
    return reduce(lambda x,y:x*y, range(1, n+1) )

def nam(n, m):
    """
    Arrangement
    n: total ememet count
    m: selected element count
    """
    return reduce(lambda x,y:x*y, range(n+1-m, n+1) )

def ncm(n, m):    
    """
    Combination
    n: total ememet count
    m: selected element count
    """
    return reduce(lambda x,y:x*y, range(n+1-m, n+1) )/factorial(m)

def take_x_pair(x):
    """
    Combination count of select x pire of general from one force
    """
    return ncm(15, x*2) * reduce(lambda a,b:a*b, 
            [ncm(n*2, 2) for n in range(1, x+1)]) / factorial(x)
 

#def p44():
#    return ncm(4,2) * pow(take_x_pair(4), 2)
#
#def p431():
#    return (nam(4,3) * take_x_pair(4) * take_x_pair(3) * take_x_pair(1) +
#            nam(4,2) * take_x_pair(5) * take_x_pair(3) )
#
#def p422():
#    return ncm(4,1) * take_x_pair(4) * ncm(3,2) * pow(take_x_pair(2), 2)
#
#def p332():
#    return ncm(4,1) * take_x_pair(1) * ncm(3,2) * pow(take_x_pair(3), 2)

def p(x):
    """
    Combination count of one specific player proportion between different force
    x: an ordered array(tuple) contain each force of player count
    """
    result = ncm(4, len(x) )
    for i in x:
        result *= take_x_pair(i)
    return result

def main():
    # all possible proportion
    x = { '44':   ((4,4),),
          # three force, or two force with one careesit 
          '431':  ((4,3,1), (5,3) ), 
          '422':  ((4,2,2),),
          '332':  ((3,3,2),),
          # four force, or three force with one careesit or two force with
          # two careesit 
          '4211': ((4,2,1,1), (5,2,1), (6,2) ), 
          '3311': ((3,3,1,1),),
          '3221': ((3,2,2,1),),
          '2222': ((2,2,2,2),),
          # four force whth one careesit, or three force with two careesit 
          # or two force with three careesit 
          '41111':((5,1,1,1), (6,1,1), (7,1) ), 
          }
    sum = 0;
    for k, v in x.items():
        x[k] = 0
        for i in v:
            x[k] += p(i)
        sum += x[k]
    print '   sum:%20d' % sum
    for k, v in sorted(x.items(), key=lambda x:x[1], reverse=True):
        print '%6s:%20d %5f%%' % (k, v, float(v)*100/float(sum) )

def choice_general():
    n = [0] * 15 + [1]* 15 + [2]* 15 + [3]*15
    s = random.sample(n, 40)
    f = {0:0,1:0, 2:0, 3:0}
    for i in range(0, 8):
        c = {0:0,1:0, 2:0, 3:0}
        for j in range(0, 5):
            c[s[i*5+j]] += 1
        c = map(lambda x:x[0], filter(lambda x:x[1]>=2, c.items()) )
        f[random.choice(c)] += 1
    return ''.join([str(x) if x!= 0 else '' for x in sorted(f.values(),
        reverse=True)])

def emulate():
    m = {'71':'41111', '62':'4211', '611':'41111', 
            '53':'431', '521':'4211', '5111':'41111'}
    x = {}
    sum = 100000
    for i in range (0, sum):
        a = choice_general()
        if a in m:
            a = m[a]
        if a in x:
            x[a] += 1
        else:
            x[a] = 1
    print '   sum:%20d' % sum
    for k, v in sorted(x.items(), key=lambda m:m[1], reverse=True):
        print '%6s:%20d %5f%%' % (k, v, float(v)*100/float(sum) )



if __name__ == '__main__':
    print '----------caculate------------'
    main()
    print '----------emulate--------------'
    emulate()

